import time


class Solution:
    def addOperators(self, num: str, target: int) -> list:
        """会超时"""
        fuhao_list = ["", "+", "-", "*"]
        mid_list = [list(num)]
        res_list = []
        length = len(num)
        for i in range(1, length):
            for j in fuhao_list:
                for lists in mid_list:
                    res_list.append(lists[:])
                    res_list[-1][i] = j + res_list[-1][i]
            mid_list = res_list[:]
        final_list = []
        for lists in res_list:
            try:
                mid_str = "".join(lists)
                mid_rse = eval(mid_str)
                if mid_rse == target:
                    final_list.append(mid_str)
            except:
                pass
        return final_list


class Solution2:
    def addOperators(self, num: str, target: int) -> list:
        if not num:
            return []
        if num == str(target):
            return [num]
        if num == str(abs(target)):
            return []
        self.res = []
        self.target = target
        self.search(num[1:], num[0], int(num[0]), int(num[0]), None, num[0] == "0")
        return self.res

    def search(self, num_in: str, lstr: str, now_val: int, last_num: int, multi_base, started_with_zero: bool):
        if not num_in:
            if now_val == self.target:
                self.res.append(lstr)
            return
        if now_val != eval(lstr):
            print(now_val, eval(lstr))
        num = int(num_in[0])
        # 加法
        self.search(num_in[1:], lstr + "+" + num_in[0], now_val + num, num, None, num == 0)
        # 减法
        self.search(num_in[1:], lstr + "-" + num_in[0], now_val - num, -num, None, num == 0)
        # 乘法
        if not multi_base:
            self.search(num_in[1:], lstr + "*" + num_in[0], now_val=now_val + last_num * (num - 1),
                        last_num=num, multi_base=last_num * num, started_with_zero=(num == 0))
        else:
            self.search(num_in[1:], lstr + "*" + num_in[0], now_val=now_val + multi_base * (num - 1),
                        last_num=num, multi_base=multi_base * num, started_with_zero=(num == 0))
        # 直接附加在后面
        if not started_with_zero:
            fuhao = -1 if last_num < 0 else 1
            if not multi_base:
                self.search(num_in[1:], lstr + num_in[0], now_val=now_val + last_num * 9 + num * fuhao,
                            last_num=last_num * 10 + num * fuhao, multi_base=None, started_with_zero=False)
            else:
                self.search(num_in[1:], lstr + num_in[0],
                            now_val=now_val - multi_base + (multi_base / last_num) * (last_num * 10 + num),
                            last_num=last_num * 10 + num, multi_base=multi_base * 10 + num * (multi_base / last_num),
                            started_with_zero=False)


a = Solution2()
print(a.addOperators(num="123", target=6))
print(a.addOperators(num="232", target=8))
print(a.addOperators(num="105", target=5))
print(a.addOperators("3456237490", 9191))
now = time.time()
print(a.addOperators("2147483647", -2147483647))
print(time.time() - now)
print(a.addOperators("000", 0))

